<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta name="description" content="关于 Lucas 定理及其扩展，BSGS及其扩展，快速质因数分解 Pollard-Rho，素性测试以及原根和阶的一些可爱知识。">
<meta property="og:type" content="article">
<meta property="og:title" content="「学习总结」数论">
<meta property="og:url" content="2020/%E3%80%8C%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93%E3%80%8D%E6%95%B0%E8%AE%BA/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:description" content="关于 Lucas 定理及其扩展，BSGS及其扩展，快速质因数分解 Pollard-Rho，素性测试以及原根和阶的一些可爱知识。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-12-20T15:41:12.000Z">
<meta property="article:modified_time" content="2021-01-09T13:15:04.950Z">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="学习总结">
<meta property="article:tag" content="数学">
<meta property="article:tag" content="数论">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="2020/「学习总结」数论/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>「学习总结」数论 | Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E6%95%B0%E8%AE%BA"><span class="nav-number">1.</span> <span class="nav-text">数论</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Lucas-%E5%AE%9A%E7%90%86"><span class="nav-number">1.1.</span> <span class="nav-text">Lucas 定理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%89%A9%E5%B1%95-Lucas-%E5%AE%9A%E7%90%86"><span class="nav-number">1.2.</span> <span class="nav-text">扩展 Lucas 定理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#BSGS"><span class="nav-number">1.3.</span> <span class="nav-text">BSGS</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%89%A9%E5%B1%95-BSGS"><span class="nav-number">1.4.</span> <span class="nav-text">扩展 BSGS</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Miller-Rabin"><span class="nav-number">1.5.</span> <span class="nav-text">Miller_Rabin</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Pollard-Rho"><span class="nav-number">1.6.</span> <span class="nav-text">Pollard-Rho</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%98%B6"><span class="nav-number">1.7.</span> <span class="nav-text">阶</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8E%9F%E6%A0%B9"><span class="nav-number">1.8.</span> <span class="nav-text">原根</span></a></li></ol></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2020/「学习总结」数论/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          「学习总结」数论
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-12-20 23:41:12" itemprop="dateCreated datePublished" datetime="2020-12-20T23:41:12+08:00">2020-12-20</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-01-09 21:15:04" itemprop="dateModified" datetime="2021-01-09T21:15:04+08:00">2021-01-09</time>
      </span>

  
    <span id="2020/「学习总结」数论/" class="post-meta-item leancloud_visitors" data-flag-title="「学习总结」数论" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2020/「学习总结」数论/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2020/「学习总结」数论/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>11k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>10 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <p>关于 <code>Lucas</code> 定理及其扩展，<code>BSGS</code>及其扩展，快速质因数分解 <code>Pollard-Rho</code>，素性测试以及原根和阶的一些可爱知识。</p>
<a id="more"></a>
<h1 id="数论"><a href="#数论" class="headerlink" title="数论"></a>数论</h1><h2 id="Lucas-定理"><a href="#Lucas-定理" class="headerlink" title="Lucas 定理"></a>Lucas 定理</h2><p>解决模数为小质数的组合数取模问题。</p>
<p>设模数为 $P$，设<br>$\begin{equation}n = \sum_{i \ge 0}\limits{a_i P^i}, m = \sum_{i \ge 0}\limits{b_i P^i}\notag\end{equation}$<br>$\begin{equation}\label{Lucas}\dbinom{n}{m} \equiv \prod_{i \ge 0}\limits{\dbinom{a_i}{b_i}} ( mod\ P)\end{equation}$<br>同时 $(\ref{Lucas})$ 还有一种形式化的写法：<br>$\begin{equation}\label{Luacs_ex}\dbinom{n}{m} \equiv \dbinom{\lfloor n/P\rfloor}{\lfloor m/P\rfloor}\dbinom{n \mod P}{m \mod P}(mod\ P)\end{equation}$</p>
<p>若小组合数可以 $\mathcal{O}(1)$ 查询，<code>Luacs</code> 的时间复杂度为 $\mathcal{O}(\log_p(n))$ 。</p>
<p>取模后不能保证 $n \ge m$ ，查询组合数要写的细致一点。</p>
<p>特殊地，如果模数是 $2$ ，根据 $(\ref{Lucas})$ 考虑如果把数字进行二进制拆分求组合数，不难发现其在模 $2$ 意义下的值为 $\left[(n\ \And\ m) = m\right]$ 其中 $n, m$ 的意义同 $(\ref{Lucas})$。</p>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">int</span> <span class="token function">_C_</span><span class="token punctuation">(</span><span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>m <span class="token operator">&lt;</span> n<span class="token punctuation">)</span>  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> frac<span class="token punctuation">[</span>m<span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> ifrac<span class="token punctuation">[</span>n<span class="token punctuation">]</span> <span class="token operator">%</span> MOD <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> ifrac<span class="token punctuation">[</span>m <span class="token operator">-</span> n<span class="token punctuation">]</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> 
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">C</span><span class="token punctuation">(</span><span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>MOD <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>n <span class="token operator">&amp;</span> m<span class="token punctuation">)</span> <span class="token operator">==</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>m <span class="token operator">&lt;</span> n<span class="token punctuation">)</span>  <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token function">C</span><span class="token punctuation">(</span>m <span class="token operator">/</span> MOD<span class="token punctuation">,</span> n <span class="token operator">/</span> MOD<span class="token punctuation">)</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">_C_</span><span class="token punctuation">(</span>m <span class="token operator">%</span> MOD<span class="token punctuation">,</span> n <span class="token operator">%</span> MOD<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="扩展-Lucas-定理"><a href="#扩展-Lucas-定理" class="headerlink" title="扩展 Lucas 定理"></a>扩展 Lucas 定理</h2><p>解决模数为可能不为质数，且每个质数幂较小的组合数取模问题。 <del>扩展卢卡斯定理和卢卡斯定理没有关系</del><br>并没有用到 <code>Luacs</code> 的基本思想 $(\ref{Lucas})$ ，扩展 <code>Lucas</code> 定理 本质上是解决了阶乘逆元不存在的情况下，形如<br>$\begin{equation}\frac{*}{n!}\mod P\label{exl}\end{equation}$<br>式子的求值。<br>考虑组合数通项公式：</p>
<p>$\begin{equation}\dbinom{n}{m} = \frac{n!}{m! (n-m)!}\label{exC}\end{equation}$</p>
<p>限制我们不能直接求 $(\ref{exC})$ 的原因——模数不为质数，无法保证逆元存在。考虑如果让分母和模数互质就可以求出这个式子的值了。</p>
<p>首先可以对模数 $p$ 进行质因数分解，分解成形如 $p = \prod_{i\ge 0}\limits{P_i^{e_i}}$ ，先分别求模数为 $P_i^{e_i}$ 式子的值，然后 <code>CRT</code> 合并答案。</p>
<p>考虑如何求出模数为 $P_i^{e_i}$ 的值。<br>设函数 $g_p(n)$ 为 $n!$ 中质因子 $p$ 的幂次。<br>设 $a = g_p(n), b=g_p(m), c=g_p(n-m)$<br>易知：<br>$\begin{equation} \ref{exC} \equiv \frac{\frac{n!}{p^{a}}}{\frac{m!}{p^{b}} \frac{(n-m)!}{p^{c}}}\ p^{a-b-c}\  (mod \ P_i^{e_i})\label{exLucas}\end{equation}$<br>设 $k=P_i^{e_i}$ ，如果所求为 $\frac{n!}{p_i^{a}}$ 对于 $n!$ 的每一项 ($1\times 2\times 3\times 4\times 5\times \dots \times n$)，其每一项在模 $k$ 意义下的取值一定是每 $k$ 个一次循环的。<br>同时每一个 $P_i$ 的倍数都可以提出一个因子 $P_i$ 也可以轻松知道，这个提出来的因子有 $\lfloor\frac{n}{P_i}\rfloor$ 个， 即 $P^{\lfloor\frac{n}{P_i}\rfloor}$ 这个式子不计入答案。<br>这些倍数提出一个 $P_i$ 的因子之后一定会形成另一个阶乘的形式，这是一个子问题，可以递归计算。剩下的数字可以暴力计算一个周期，然后根据周期的出现次数，直接计算式子的值。 这样就可以算出 $n!$ 去掉所有质因子 $P_i$ 在模 $P_i^{e_i}$ 意义下的值了。 保证了这个值和 $P_i$ 互质，这样就可以求逆元了。<br>根据 $(\ref{exLucas})$ 计算即可。</p>
<p>关于函数 $g_p(n)$ 的计算：<br>$g_p(n) = \prod_{i\ge 1}\limits{\lfloor\frac{n}{p^i}\rfloor}= \frac{n - f_p(n)}{p - 1}$，其中 $f_p(n)$ 为数字 $n$ 在 $p$ 进制下的数位和。</p>
<p>注意逆元不是质数，别<del>傻不拉几的</del>冲一个费马小定理。</p>
<p>复杂度是 $\mathcal{O}\left(\sum_{i\ge 0}\limits{(\log P + P_i^{e_i})\log n}\right)$ 大概就是 $\mathcal{O}\left(\sum_{i \ge 0}\limits{P_i^{e_i}\log n}\right)$ 吧。</p>
<details class="note info"><summary><p>code</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">int</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">int</span> p<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> ans <span class="token operator">+=</span> n <span class="token operator">%</span> p<span class="token punctuation">;</span> n <span class="token operator">/=</span> p<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">g</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token punctuation">(</span>P <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">pow</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a <span class="token operator">%</span> P<span class="token punctuation">;</span> a <span class="token operator">=</span> a <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a <span class="token operator">%</span> P<span class="token punctuation">;</span> b <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token comment">//int inv(int x, int MOD) &#123; return pow(x, MOD - 2, MOD); &#125; // deleted: Fermat's Little Theorem is NOT correct when MOD is not a prime number.</span>
<span class="token keyword">int</span> <span class="token function">exgcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">&amp;</span>x<span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">&amp;</span>y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> x <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> y <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">return</span> a<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token keyword">int</span> g <span class="token operator">=</span> <span class="token function">exgcd</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> a <span class="token operator">%</span> b<span class="token punctuation">,</span> y<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
	y <span class="token operator">-=</span> <span class="token punctuation">(</span>a <span class="token operator">/</span> b<span class="token punctuation">)</span> <span class="token operator">*</span> x<span class="token punctuation">;</span>
	<span class="token keyword">return</span> g<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">inv</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">// add: Exgcd</span>
	<span class="token keyword">int</span> x<span class="token punctuation">,</span> y<span class="token punctuation">;</span> <span class="token function">exgcd</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> P<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token punctuation">(</span>x <span class="token operator">%</span> P <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> P <span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">calc</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">int</span> p<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">// calc n!(without p) mod p^k</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> P <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token function">rep</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> k<span class="token punctuation">)</span> P <span class="token operator">*=</span> p<span class="token punctuation">;</span>
	<span class="token keyword">int</span> res <span class="token operator">=</span> n <span class="token operator">%</span> P<span class="token punctuation">,</span> prd0 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> prd1 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> 
	<span class="token function">rep</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">%</span> p <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">&lt;=</span> res<span class="token punctuation">)</span> prd0 <span class="token operator">=</span> prd0 <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> i <span class="token operator">%</span> P<span class="token punctuation">;</span>
		prd1 <span class="token operator">=</span> prd1 <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> i <span class="token operator">%</span> P<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token function">calc</span><span class="token punctuation">(</span>n <span class="token operator">/</span> p<span class="token punctuation">,</span> p<span class="token punctuation">,</span> k<span class="token punctuation">)</span><span class="token punctuation">;</span>
	ans <span class="token operator">=</span> ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> prd0 <span class="token operator">%</span> P<span class="token punctuation">;</span>
	ans <span class="token operator">=</span> ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">pow</span><span class="token punctuation">(</span>prd1<span class="token punctuation">,</span> n <span class="token operator">/</span> P<span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span> <span class="token comment">// changed `pow(prd1, n / p, P)` to `pow(prd1, n / P, P) % P`.</span>
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
LL n<span class="token punctuation">,</span> m<span class="token punctuation">;</span> <span class="token keyword">int</span> MOD<span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> <span class="token operator">></span> d<span class="token punctuation">;</span>
<span class="token keyword">namespace</span> Divide<span class="token punctuation">&#123;</span>
	<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">1e6</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> np<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> prime<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> Mid<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token function">rep</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>np<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> prime<span class="token punctuation">[</span><span class="token operator">++</span>tot<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">,</span> Mid<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">;</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> tot <span class="token operator">&amp;&amp;</span> prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">*</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
				<span class="token keyword">int</span> x <span class="token operator">=</span> prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">*</span> i<span class="token punctuation">;</span> Mid<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
				np<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
				<span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">%</span> prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">break</span><span class="token punctuation">;</span>
			<span class="token punctuation">&#125;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">void</span> <span class="token function">divide</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> <span class="token operator">></span> <span class="token operator">&amp;</span> res<span class="token punctuation">,</span> <span class="token keyword">int</span> MOD<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tot<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>MOD <span class="token operator">%</span> prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
			pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> ans<span class="token punctuation">;</span> ans<span class="token punctuation">.</span>fi <span class="token operator">=</span> prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
			ans<span class="token punctuation">.</span>se <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
			<span class="token keyword">while</span><span class="token punctuation">(</span>MOD <span class="token operator">%</span> prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> MOD <span class="token operator">/=</span> prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> ans<span class="token punctuation">.</span>se<span class="token operator">++</span><span class="token punctuation">;</span>
			res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span><span class="token comment">// 这里可以直接 $\mathcal&#123;O&#125;(\sqrt&#123;n&#125;)$ 试除即可，没必要分解质因数。写的时候太年轻了。</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">CRT</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> <span class="token operator">></span> <span class="token operator">&amp;</span> A<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> W <span class="token operator">=</span> MOD<span class="token punctuation">;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token function">rep</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> A<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> now <span class="token operator">=</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
		ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token punctuation">(</span> now<span class="token punctuation">.</span>fi <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token punctuation">(</span>W <span class="token operator">/</span> now<span class="token punctuation">.</span>se<span class="token punctuation">)</span> <span class="token operator">%</span> MOD <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">inv</span><span class="token punctuation">(</span>W <span class="token operator">/</span> now<span class="token punctuation">.</span>se<span class="token punctuation">,</span> now<span class="token punctuation">.</span>se<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> <span class="token operator">></span> Ans<span class="token punctuation">;</span>
<span class="token keyword">signed</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">//freopen(".in", "r", stdin);</span>
	<span class="token function">Read</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">(</span>MOD<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token class-name">Divide</span><span class="token operator">::</span><span class="token function">init</span><span class="token punctuation">(</span>MOD <span class="token operator">+</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token class-name">Divide</span><span class="token operator">::</span><span class="token function">divide</span><span class="token punctuation">(</span>d<span class="token punctuation">,</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">rep</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> d<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> NowMod <span class="token operator">=</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> P <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>se<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> rA <span class="token operator">=</span> <span class="token function">calc</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>se<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> rB <span class="token operator">=</span> <span class="token function">calc</span><span class="token punctuation">(</span>n <span class="token operator">-</span> m<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>se<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> rC <span class="token operator">=</span> <span class="token function">calc</span><span class="token punctuation">(</span>m<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>se<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
		ans <span class="token operator">=</span> rA <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">inv</span><span class="token punctuation">(</span>rB<span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">inv</span><span class="token punctuation">(</span>rC<span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span>
		ans <span class="token operator">=</span> ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">pow</span><span class="token punctuation">(</span>NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">,</span> <span class="token function">g</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token function">g</span><span class="token punctuation">(</span>n <span class="token operator">-</span> m<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token function">g</span><span class="token punctuation">(</span>m<span class="token punctuation">,</span> NowMod<span class="token punctuation">.</span>fi<span class="token punctuation">)</span><span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span>
		Ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">mp</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span> <span class="token function">CRT</span><span class="token punctuation">(</span>Ans<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>


<h2 id="BSGS"><a href="#BSGS" class="headerlink" title="BSGS"></a>BSGS</h2><p>求解模数为质数的指数方程。$a^x \equiv b\ (mod\ p) \ p \in P$。<br>由欧拉定理可知，本质不同的解 范围为 $[0, p-1]$ 。<br>朴素做法就是枚举一下 $[0, p-1]$ 判断是不是解，但是这样显然太慢了。<br>考虑选一个参数 $T$，则 $\forall x \in [0, p-1]$ 都可以表示成 $r \times T + c\ \ (b &lt; T)$ 的形式，易知，$r = \lfloor\frac{x}{T} \rfloor, c=x\ mod \ T$</p>
<p>带入原式： </p>
<p>$$<br>\begin{equation*}<br>a^{rT + c} \equiv b\ (mod\ p)<br>\end{equation*}<br>$$<br>$$<br>\begin{equation} \label{BSGS0}<br>a^{c} \equiv b\times a^{-rT}\ (mod\ p)<br>\end{equation}<br>$$<br>可以考虑枚举 $c$ 算出每一个 $a^{c}$ 压入 <code>set</code> 或 <code>hash</code> 表，然后枚举每一个 $r$ 算出每一个 $a^{-rT} \times b$  在之前算出的答案中查找，如果能找到相同的取值（即：满足$(\ref{BSGS0})$），就说明当前这个 $r$ 就是一个答案。</p>
<details class="note info"><summary><p>code</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">int</span> <span class="token function">inv</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> x<span class="token punctuation">,</span> y<span class="token punctuation">;</span> <span class="token function">exgcd</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> P<span class="token punctuation">,</span> x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token punctuation">(</span>x <span class="token operator">%</span> P <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">BSGS</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token comment">// a^x = b (mod P) (a, p) = 1;</span>
	<span class="token keyword">static</span> set<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">></span> S<span class="token punctuation">;</span> S<span class="token punctuation">.</span><span class="token function">clear</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> T <span class="token operator">=</span> <span class="token function">sqrt</span><span class="token punctuation">(</span>P<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> x <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> T<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> x <span class="token operator">=</span> x <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a <span class="token operator">%</span> P<span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">!=</span> b<span class="token punctuation">)</span> S<span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">else</span> <span class="token keyword">return</span> i<span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> T<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> now <span class="token operator">=</span> b <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">inv</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> T <span class="token operator">*</span> i<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>S<span class="token punctuation">.</span><span class="token function">count</span><span class="token punctuation">(</span>now<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i <span class="token operator">*</span> T<span class="token punctuation">,</span> V <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> j<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">,</span> V <span class="token operator">=</span> V <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a <span class="token operator">%</span> P<span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>V <span class="token operator">==</span> b<span class="token punctuation">)</span> <span class="token keyword">return</span> j<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>

<h2 id="扩展-BSGS"><a href="#扩展-BSGS" class="headerlink" title="扩展 BSGS"></a>扩展 BSGS</h2><p>用于求解模数不一定为质数的指数方程。$a^x \equiv b\ (mod\ p) \ p \in P$。<br>限制不能直接 $BSGS$ 的因素就是不能保证逆元存在，那就考虑如何让 $(a, p) = 1$ 。</p>
<p>具体地，设 $d_1=\gcd(a,p)$ 。如果 $d_1\nmid b$ ，则原方程无解。否则我们把方程同时除以 $d_1$ ，得到<br>$$<br>\begin{equation}<br>\frac{a}{d_1}\cdot a^{x-1}\equiv \frac{b}{d_1}\pmod{\frac{p}{d_1}}<br>\end{equation}<br>$$</p>
<p>如果 $a$ 和 $\frac{p}{d_1}$ 仍不互质就再除，设 $d_2=\gcd\left(a,\frac{p}{d_1}\right)$ 。如果 $d_2\nmid \frac{b}{d_1}$ ，则方程无解；否则同时除以 $d_2$ 得到.<br>$$<br>\begin{equation}<br>\frac{a^2}{d_1d_2}\cdot a^{x-2}≡\frac{b}{d_1d_2} \pmod{\frac{p}{d_1d_2}}<br>\end{equation}<br>$$<br>直到模数和 $a$ 互质。 记 $D = \prod\limits{d_i}$，则</p>
<p>$$<br>\begin{equation}<br>\frac{a^k}{D}\cdot a^{x-k}\equiv\frac{b}{D} \pmod{\frac{p}{D}}<br>\end{equation}<br>$$<br>就可以使用 <code>BSGS</code> 求解了。</p>
<p>需要注意的是：</p>
<ul>
<li>解可能小于 $k$ ，可以暴力枚举一下小于 $k$ 的幂次，判断一下</li>
<li>如果有 $d_i$ 不是 $b$ 的约数，直接判断无解即可。</li>
</ul>
<pre class="line-numbers language-none"><code class="language-none">int exBSGS(int a, int b, int P)&#123; 
	int D &#x3D; 1, k &#x3D; 0, tp &#x3D; P;
	while(true) &#123; int g &#x3D; gcd(a, tp); if(g &#x3D;&#x3D; 1) break; tp &#x2F;&#x3D; g; D *&#x3D; g; k++;  &#125;
	for(int i &#x3D; 0, V &#x3D; 1; i &lt;&#x3D; k; i++, V &#x3D; V *1ll* a % P) if(V &#x3D;&#x3D; b) return i; &#x2F;&#x2F; changed: It must be executed before &#96;if(b % D !&#x3D; 0) return -1&#96;).
	int S &#x3D; pow(a, k, tp);
	if(b % D !&#x3D; 0) return -1; &#x2F;&#x2F; added: It is necessary!
	int B &#x3D; b *1ll* inv(S, tp) % tp;
	int r &#x3D; BSGS(a, B, tp);
	return r &#x3D;&#x3D; -1 ? -1 : r + k;
&#125;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>已通过 luogu 和 SPOJ 的测试数据，但是 zhx (Orz) 的数据只有 $50pts$  待填。</p>
<p>$\begin{equation}\label{} \end{equation}$</p>
<h2 id="Miller-Rabin"><a href="#Miller-Rabin" class="headerlink" title="Miller_Rabin"></a>Miller_Rabin</h2><p>快速判断大数素性。</p>
<p>一个结论：<br>如果 $n$ 为质数 $\forall a &lt; n$ 设 $n - 1 = d \times 2^r, (d, 2) = 1$，则<br>$\begin{equation}\label{MR0}a^d \equiv 1 \pmod n \end{equation}$<br>$\begin{equation}\label{MR1}\exists\ 0 \le i &lt; r, s.t. a^{d\times i^i} \equiv -1 \pmod n \end{equation}$<br>$\ref{MR0}$ 和 $\ref{MR1}$ 至少一个满足。<br>是否为充要条件带查。</p>
<p>我们需要判断一个数是否为质数，只需要判断是否符合上面的定理即可，但是 $\forall a &lt; n$ 对复杂度不友好。</p>
<p>通常的做法是选择若干质数当作底数 $a$，进行判断。</p>
<p>关于底数的选择：</p>
<blockquote>
<p>如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46 856 248 255 981 ——matrix67博客 (Orz)</p>
</blockquote>
<p>选择 <code>int PrimeList[10] = &#123;2, 3, 7, 61, 24251, 11, 29&#125;;</code> 即可，或者再随意加几个小质数。</p>
<p>需要注意快速乘法的实现。<br>复杂度为 $\mathcal{O}(k \log x)$</p>
<details class="note info"><summary><p>code</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">LL <span class="token keyword">long</span> <span class="token keyword">long</span> </span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">ULL <span class="token keyword">unsigned</span> <span class="token keyword">long</span> <span class="token keyword">long</span> </span></span>
<span class="token keyword">inline</span> ULL <span class="token function">mul</span><span class="token punctuation">(</span>ULL a<span class="token punctuation">,</span> ULL b<span class="token punctuation">,</span> ULL MOD<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token comment">// unsigned long long  </span>
	LL R <span class="token operator">=</span> <span class="token punctuation">(</span>LL<span class="token punctuation">)</span>a<span class="token operator">*</span>b <span class="token operator">-</span> <span class="token punctuation">(</span>LL<span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token punctuation">(</span>ULL<span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">double</span><span class="token punctuation">)</span>a <span class="token operator">*</span> b <span class="token operator">/</span> MOD<span class="token punctuation">)</span> <span class="token operator">*</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token comment">// 只关心两个答案的差值，这个差值一定小于 unsigned long long 的最大值，</span>
	<span class="token comment">// 所以在哪个剩余系下都不重要，不管差值是什么都能还原出原始数值。 </span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>R <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> R <span class="token operator">+=</span> MOD<span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>R <span class="token operator">></span> MOD<span class="token punctuation">)</span> R <span class="token operator">-=</span> MOD<span class="token punctuation">;</span>
	<span class="token keyword">return</span> R<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> LL <span class="token function">pow</span><span class="token punctuation">(</span>LL a<span class="token punctuation">,</span> LL b<span class="token punctuation">,</span> LL P<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> LL ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token function">mul</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> a<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">;</span> a <span class="token operator">=</span> <span class="token function">mul</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> a<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">;</span> b <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> PrimeList<span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">&#123;</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">61</span><span class="token punctuation">,</span> <span class="token number">24251</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">19</span><span class="token punctuation">,</span> <span class="token number">29</span><span class="token punctuation">,</span> <span class="token number">27</span><span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
<span class="token keyword">bool</span> <span class="token function">Miller_Rabin</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> LL n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	LL d <span class="token operator">=</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> r <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> x<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token punctuation">(</span>d <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span> d <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token operator">++</span><span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span>x <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span> d<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> t <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> t <span class="token operator">&lt;=</span> r<span class="token punctuation">;</span> t<span class="token operator">++</span><span class="token punctuation">,</span> x <span class="token operator">=</span> <span class="token function">mul</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> x<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">==</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">bool</span> <span class="token function">Prime</span><span class="token punctuation">(</span>LL x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">&lt;=</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token keyword">return</span> x <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">7</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">==</span> PrimeList<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">Miller_Rabin</span><span class="token punctuation">(</span>PrimeList<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>

<h2 id="Pollard-Rho"><a href="#Pollard-Rho" class="headerlink" title="Pollard-Rho"></a>Pollard-Rho</h2><p>快速分解质因数的解决方案。<br>复杂度 $\mathcal{O}(Accepted)$。大约为 $\mathcal{O}(n^{1/4})$ ，算法导论给出的是 $\mathcal{O}(\sqrt{n})$，但是随机数据下，$1s$ 分解 $10000$ 个 $10^{18}$ 量级的数字问题不大……</p>
<blockquote>
<p>任何一个伟大的算法都来自于一个微不足道的猜想。</p>
</blockquote>
<p>考虑给出一个数字 $n$ ，如果可以快速找其中一个因子 $g$ ，然后继续递归分解 $n / g$ 和 $g$ 即可完成质因数分解。</p>
<p>考虑如何快速寻找一个数 $n$ 的因子 $g$； （以下复杂度分析都是基于最坏情况，即素数平方的形式）</p>
<ol>
<li>枚举 $n$ 的因子 $g$ 试除，复杂度为 $\mathcal{O}(\sqrt{n})$</li>
<li>考虑随机枚举 $n$ 的因子，试除，期望复杂度为 $\mathcal{O}(n)$</li>
<li>没必要随机枚举 $n$ 的因子，只需要随机一个数字 $a$ 那么 $g = gcd(a, n)$ 就是 $n$ 的一个因子，需要找到一个不平凡的因子才可以，这样 $a$ 的合法取值变成了 $n$ 的因子或 $n$ 因子的倍数，合法的 $a$ 的取值有 $\mathcal{O}(\sqrt{n})$ 个。</li>
</ol>
<p>着重考虑下一种优化：</p>
<p>考虑一次性随机出 $k$ 个数字 分别记作 $a_{1…k}$，考虑其中两两的差值，应该有 $k^2$ 种差值。试图让其差值与 $n$ 求最大公约数 $c$，若 $c$ 不为 $1$ 则 $c$ 就是一个不平凡因子。<br>差值与 $n$ 的最大公约数为 $c$，等价于 差值在 $c$ 的剩余系下同余 $0$。考虑这 $k^2$ 个差值都不等于 $0$ 的概率为多少。因为这 $k$ 个数字是随机的，那么他们差值的取值在 $c$ 的剩余系下也是在 $[0, c]$ 等概率分布的。那么都不等于 $0$ 的概率为 $\left(\frac{c - 1}{c}\right)^{k^2}$。最坏情况下，合法的 $c$ 只有一个，且等于 $\sqrt{n}$ 根据<br>$\begin{equation}\left(\frac{n-1}{n}\right)^{n} \approx \frac{1}{e}\end{equation}$<br>当 $k = n^{1/4}$ 时，取不到值得概率为 $\frac{1}{e}$。稍微增大几倍的 $k$ 可以降低找不到概率。 注意这样的做法需要枚举所有 $k^2$ 对差值，再加上判断和取不到约数情况的出现，复杂度要劣于 $\mathcal{O}(\sqrt{n})$。<br>枚举 $k^2$ 对差值是上面算法的瓶颈。引入伪随机函数 $f(x) = f^2(x-1) + c \mod n$。<br>这个函数有几点比较优良性质：</p>
<ol>
<li>仍然可以看成是一种随机函数，保证了上面推导中对随机的依赖性。<del>（个人感觉不能保证完全随机……）</del></li>
<li>经过一段次数的递推之后会进入一个循环，因为之和前一项的值有关，而且取值只能在 $[0, n-1]$ 内，所以至多 $\mathcal{O}(n)$ 次递推，一定会进入一个循环。</li>
<li>$g \mid f(i) - f(j)\ \ \  \Rightarrow\ \ \ g \mid f(i + 1) - f(j - 1)$  证明：<br>$f(i + 1) - f(j + 1) = (f^2(i) + c) - (f^2(j) + c) = (f(i) - f(j))(f(i) + f(j))$<br>也就是 $g$ 是否为某两个差值的约数之和两个差值下标的差有关。</li>
</ol>
<p>考虑两个指针，分别为 $L, R$ ，每次 $L$ 递推一个， $R$ 递推两个，因为函数存在环，这两个差值总会在环上相遇，从开始到相遇之间的时间，每次执行后，判断其差值与 $n$ 的 <code>gcd</code> 是否不等于 $1$ 即可。相遇所需时间，即环的大小约为 $\sqrt{n}$ 。环的大小决定运行最坏时间。</p>
<p>这样还是不够快，其实不需要每次执行都算一下 $gcd$ 可以执行一些步数之后，将其差值乘到一起，一起求 $gcd$ 即可，可以证明，这样的变化保证答案不会变劣。<br>考虑让两个指针倍增的往前跳，倍增若干次后，每次计算两个指针距离之间的所有差值取值，乘在一起计算 $gcd$。</p>
<p><del>标准代码中：差值相同的解会计算多次。但是确实大大提升运行效率。这里就不会分析了，但是直观感觉就是，其实那个函数往后递推的次数越多会包含更多的因子。也就是说，如果两对函数值差值下标距离一样，其实下标大的那一对会更优。</del> 总的来说，快的玄学。</p>
<p>可以写出如下代码：</p>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp">LL <span class="token function">Pollard_Rho</span><span class="token punctuation">(</span>LL n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	LL c <span class="token operator">=</span> <span class="token function">rand</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
	LL L <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> s <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> t <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> s <span class="token operator">&lt;&lt;=</span> <span class="token number">1</span><span class="token punctuation">,</span> t <span class="token operator">&lt;&lt;=</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		LL R <span class="token operator">=</span> L<span class="token punctuation">,</span> M <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> s<span class="token punctuation">,</span> step <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> t<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> step <span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			R <span class="token operator">=</span> <span class="token function">f</span><span class="token punctuation">(</span>R<span class="token punctuation">,</span> c<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
			M <span class="token operator">=</span> <span class="token function">mul</span><span class="token punctuation">(</span>M<span class="token punctuation">,</span> <span class="token function">abs</span><span class="token punctuation">(</span>L <span class="token operator">-</span> R<span class="token punctuation">)</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>step <span class="token operator">%</span> <span class="token number">1000</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> LL g <span class="token operator">=</span> <span class="token function">gcd</span><span class="token punctuation">(</span>M<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>g <span class="token operator">></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> g<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
			<span class="token comment">// 不一定必须等到一轮计算结束之后再计算 gcd 可能中间就已经出现答案了，中间每隔一段时间算几次，可以在出现答案之后快速返回答案。</span>
		<span class="token punctuation">&#125;</span>
		LL g <span class="token operator">=</span> <span class="token function">gcd</span><span class="token punctuation">(</span>M<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>g <span class="token operator">></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> g<span class="token punctuation">;</span>
		L <span class="token operator">=</span> R<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">factorize</span><span class="token punctuation">(</span>LL n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">Prime</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	LL g <span class="token operator">=</span> n<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>g <span class="token operator">==</span> n<span class="token punctuation">)</span> g <span class="token operator">=</span> <span class="token function">Pollard_Rho</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">factorize</span><span class="token punctuation">(</span>g<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">factorize</span><span class="token punctuation">(</span>n <span class="token operator">/</span> g<span class="token punctuation">)</span><span class="token punctuation">;</span> 
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="阶"><a href="#阶" class="headerlink" title="阶"></a>阶</h2><p>若 $a \perp P$，则使 $a^k \equiv 1 \pmod P$ 成立的最小的 $k$，称为 $a$ 关于模 $P$ 的阶，记作 $\text{ord}_m(a)$。</p>
<p>求法： 根据欧拉定理，$\text{ord}_m(a) \mid \varphi(m)$，先求出 $\varphi(m)$，记作 $t$。</p>
<ul>
<li>枚举 $t$ 的每一个因子，检查是否满足阶的性质。</li>
<li>对 $t$ 质因数拆分，以此考虑每个质因子，试图减少质因子的幂次——即如果减少了某个质因子的幂次，$a^t \equiv 1 \pmod P$ 依然成立，那么就直接减少即可。感性理解一下肯定是对的。 $\mathcal{O}(\log \varphi(P))$</li>
</ul>
<h2 id="原根"><a href="#原根" class="headerlink" title="原根"></a>原根</h2><p>若 $\text{ord}_mg = \varphi(m)$ 则称 $g$ 为 $m$ 的原根。</p>
<p>通俗的讲：称 $g$ 为 $P$ 的原根，当且仅当 ${g^0, g^1, g^2, \dots, g^{\varphi(P) - 1}}$ 数两两不同。</p>
<p>即对于任意一个和 $P$ 互质的数字，在 $P$ 的剩余系下，都可以表示成 $g^t$ 的形式。</p>
<p>一个模数存在原根，当且仅当这个模数为 $2, 4, p^s, 2p^s$，$p$ 为奇素数。</p>
<p>判断一个数是否为原根：根据定义可以考虑枚举每一个 $t \in [1, \varphi(P) - 1]$ 判断 $g^t$ 是否都不等于 $1$。事实上，根据欧拉定理，可能使 $g^t \equiv 1 \pmod P$ 的 $t$ 只可能是是 $\varphi(P)$ 的约数。枚举 $\varphi(P)$ 的每个约数，进行判断即可，复杂度为 $\mathcal{O}(\sqrt{\varphi(P)})$</p>
<p>原根的求法：若一个数 $m$ 存在原根，其最小原根大概在 $m^{1/4}$ 级别。枚举原根再判断一般是可以接受的。</p>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">bool</span> <span class="token function">JudgePrimitiveRoot</span><span class="token punctuation">(</span><span class="token keyword">int</span> g<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> phi <span class="token operator">=</span> P <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">*</span> i <span class="token operator">&lt;=</span> phi<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>phi <span class="token operator">%</span> i <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span>g<span class="token punctuation">,</span> i<span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span> 
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span>g<span class="token punctuation">,</span> P <span class="token operator">/</span> i<span class="token punctuation">,</span> P<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">GetPrimitiveRoot</span><span class="token punctuation">(</span><span class="token keyword">int</span> P<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">JudgePrimitiveRoot</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> P<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> i<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>地位相当于自然数域下的唯一分解定理。</p>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a target="_blank" href="//tags/学习总结/" rel="tag noopener"># 学习总结</a>
              <a target="_blank" href="//tags/数学/" rel="tag noopener"># 数学</a>
              <a target="_blank" href="//tags/数论/" rel="tag noopener"># 数论</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2020/「学习总结」数据结构/" rel="prev" title="「学习总结」数据结构">
                  <i class="fa fa-chevron-left"></i> 「学习总结」数据结构
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2020/「学习总结」群 置换群/" rel="next" title="「学习总结」群 置换群">
                  「学习总结」群 置换群 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
  
  
  



      
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "2020/「学习总结」数论/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
